package edu.whu.rose.clock.ssql.graph;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Date;
import java.util.HashSet;

import com.sleepycat.bind.tuple.IntegerBinding;
import com.sleepycat.je.Cursor;
import com.sleepycat.je.DatabaseEntry;
import com.sleepycat.je.DatabaseException;
import com.sleepycat.je.LockMode;
import com.sleepycat.je.OperationStatus;

import edu.whu.rose.clock.ssql.binding.SubGraphBinding;
import edu.whu.rose.clock.ssql.index.RelationshipMatrix;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class GraphManager {

	private int radius;
	private int rank;
	
	private RelationshipMatrix graph;

	private SubGraphDB sgdb;
	private SubGraphCache cache;
	
//	private RRadiusSubGraph[] allSubGraphs;
//	private RRadiusSubGraph[] allMaxSubGraphs;
	
	private SequentialIntArray[] invertedList;
	
	private final String defaultDBEnv = "F:/data/subgraphDbEnv";
	private final String defaultEdgeFile = "F:/data/graph/edge.txt";
	
	
	public GraphManager(int radius, int rank) {
		this.radius = radius;
		this.rank = rank;
		this.graph = new RelationshipMatrix(rank);
		this.sgdb = new SubGraphDB(this.defaultDBEnv);
	}
	
	public GraphManager(int radius, int rank, String dbEnv) {
		this.radius = radius;
		this.rank = rank;
		this.graph = new RelationshipMatrix(rank);
		this.sgdb = new SubGraphDB(dbEnv);
	}
	
//	public static void main(String[] args) {
//		File file = new File("dbEnv_subgraph");
//		if (file.isDirectory()) {
//			File[] files = file.listFiles();
//			for (int i = 0; i < files.length; i++) {
//				files[i].delete();
//			}
//		}
//		
//		GraphManager gm = new GraphManager(2, 12, "dbEnv_subgraph");
//		gm.loadMatrix(new int[][]{
//				{1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
//				{1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, 
//				{0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,}, 
//				{1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0,}, 
//				{0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0,}, 
//				{0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,}, 
//				{0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0,}, 
//				{0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0,}, 
//				{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0,}, 
//				{0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1,}, 
//				{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,},
//				{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,}});
//		gm.init(2);
//		gm.genMaxSubGraphs();
//		gm.printAllSubGraphs("subgraphs.txt");
//		gm.genSubGraphInvertedList();
//		gm.printInvertedList("invlist.txt");
//		gm.close();
//		
////		gm.genInvertedList();
////		gm.printInvertedList("F:/data/il.txt");
//	}
	
	public static void main(String[] args) {
		File file = new File("dbEnv_subgraph");
		if (file.isDirectory()) {
			File[] files = file.listFiles();
			for (int i = 0; i < files.length; i++) {
				files[i].delete();
			}
		}
		
		GraphManager gm = new GraphManager(2, 198467, "dbEnv_subgraph");
		int num = gm.loadMatrix("F:/data/5000029_graph/edge.txt");
		gm.init(100000);
		gm.genMaxSubGraphs();
		System.out.println("start post-processing...");
		gm.postProc();
		System.out.println("start printing...");
		gm.printAllSubGraphs("subgraphs.txt");
		
//		gm.genSubGraphInvertedList();
//		gm.printInvertedList("invlist.txt");
//		
//		try {
//			BufferedReader br = new BufferedReader(new FileReader("graph/vertex.txt"));
//			HashSet<String> stopwordlist = new HashSet<String>();
//			BufferedReader br2 = new BufferedReader(new FileReader("stop word list.txt"));
//			while (br2.ready()) {
//				stopwordlist.add(br2.readLine().trim());
//			}
//			
//			gm.computeSGKN(br, stopwordlist);
//			
//			br2.close();
//			br.close();
//		}
//		catch (IOException ex) {
//			ex.printStackTrace();
//		}
		
		gm.close();
		System.out.println("Finished");
		System.out.println("Total number of edges: " + num);
	}
	
	public void init(int capacity) {
		if (!this.sgdb.initEnv() || !this.sgdb.openDB()) {
			System.exit(1);
		}
		this.cache = new SubGraphCache(this.rank, capacity, sgdb);
	}
	
	public void close() {
		this.sgdb.closeDB();
	}
	
	public void loadMatrix(int[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if (matrix[i][j] == 1) {
					this.graph.insert(i, j, null);
				}
			}
		}
		
	}
 	
	public void loadMatrix() {
		this.graph.load(this.defaultEdgeFile);
	}
	
	public int loadMatrix(String edgeFile) {
		return this.graph.load(edgeFile);
	}
	
	public void genMaxSubGraphs() {
		Date start = new Date();
		for (int i = 0; i < this.rank; i++) {
			RRadiusSubGraph rrsg = this.genRawSubGraph(i);
			System.out.println("generate a raw subgraph " + i);
			if (rrsg != null) {
				this.addMaxSubGraph(rrsg);
//				if (rrsg.getVertexes().length < 10) {
//					System.out.println(rrsg.getRow() + " : " + rrsg.getVertexes().length);
//				}
//				if (i >= 50000) {
//					System.out.println(i + "");
//				}
			}
		}
		this.cache.flush();
		Date end = new Date();
		System.out.println("Time exhausted: " + (end.getTime() - start.getTime()) + " ms");
		this.cache.statistic();
	}
	
	public void postProc() {
		Cursor cursor = null;
		DatabaseEntry key = new DatabaseEntry();
		DatabaseEntry value = new DatabaseEntry();
		int id = 0;
		IntegerBinding ib = new IntegerBinding();
		SubGraphBinding sgb = new SubGraphBinding();
		
		try {
			cursor = sgdb.getCursorOfSubgraphs();
			while (cursor.getNext(key, value, LockMode.DEFAULT) == OperationStatus.SUCCESS) {
				id++;
				ib.intToEntry(id, key);
				
				RRadiusSubGraph rrsg = (RRadiusSubGraph)sgb.entryToObject(value);
				int[] vertexes = rrsg.getVertexes();
				ExpandableIntArray startVertexes = new ExpandableIntArray();
				ExpandableIntArray endVertexes = new ExpandableIntArray();
				for (int i = 0; i < vertexes.length; i++) {
					int startVertex = vertexes[i];
					int[] ends = graph.getColumns(startVertex - 1);
					if (ends == null) {
//						System.err.println("Error: found isolated vertex (" + startVertex + ")");
						continue;
					}
					int[] filteredEnds = merge(ends, vertexes);
					if (filteredEnds == null) {
						continue;
					}
					for (int j = 0; j < filteredEnds.length; j++) {
						startVertexes.add(startVertex);
						endVertexes.add(filteredEnds[j]);
					}
				}
				rrsg.setStartVertexes(startVertexes.toArray());
				rrsg.setEndVertexes(endVertexes.toArray());
				sgb.objectToEntry(rrsg, value);
				
				cursor.delete();
				cursor.put(key, value);
				System.out.println("post-processed " + id);
			}
		}
		catch (DatabaseException ex) {
			ex.printStackTrace();
		}
		finally {
			try {
				if (cursor != null) {
					cursor.close();
				}
			}
			catch (DatabaseException ex) {
				ex.printStackTrace();
				System.err.println("Error: closing cursor");
			}
		}
	}
	
	public int[] merge(int[] arr1, int[] arr2) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int low = 0;
		for (int i = 0; i < arr1.length; i++) {
			int mid = 0;
			int top = arr2.length - 1;
			while (low <= top) {
				mid = (low + top) / 2;
				if (arr1[i] + 1 > arr2[mid]) {
					low = mid + 1;
				}
				else if (arr1[i] + 1 < arr2[mid]) {
					top = mid - 1;
				}
				else {
					eia.add(arr1[i] + 1);
					break;
				}
			}
		}
		return eia.toArray();
	}
	
	public void computeSGKN(BufferedReader br, HashSet<String> stopwordlist) {
		this.sgdb.computeSGKN(br, stopwordlist);
	}
	
	private void addMaxSubGraph(RRadiusSubGraph rrsg) {
		int row = rrsg.getRow() - 1;
		int[] vertexes = rrsg.getVertexes();
		int result = 0;
		boolean select = true;
		
		for (int i = 0; i < vertexes.length; i++) {
			int compRow = vertexes[i] - 1;
			if (compRow < row) {
				RRadiusSubGraph comp = cache.get(compRow);
				if (comp != null) {
					int[] compVertexes = comp.getVertexes();
					result = MyMath.compareIntArrays(vertexes, compVertexes);
					if (result == MyMath.ARR1_CONTAIN_ARR2) {
						cache.delete(compRow, true);
					}
					else if (result == MyMath.ARR2_CONTAIN_ARR1) {
						select = false;
						break;
					}
				}
			}
			else {
				break;
			}
			
		}
		
		if (select) {
			cache.insert(rrsg);
		}
		else {
			cache.delete(row, false);
		}
	}
	
	public RRadiusSubGraph genRawSubGraph(int row) {
		return this.graph.rowSearch(row, this.radius);
	}
	
	public void genSubGraphInvertedList() {
		this.sgdb.genSubGraphInvertedList(rank);
	}
	
//	public RRadiusSubGraph genSubGraph(int row) {
//		RRadiusSubGraph rrsg = this.genRawSubGraph(row);
//		
//		if (rrsg != null) {
//			int[] vertexes = rrsg.getVertexes();
//			
//			boolean select = true;
//			
//			for (int j = 0; j < vertexes.length; j++) {
//				if (this.isContained(vertexes, vertexes[j])) {
//					select = false;
//					break;
//				}
//			}
//			
//			if (select) {
//				return rrsg;
//			}
//		}
//		return null;
//	}

//	public void genSubGraphs(int rank, String rowFileName, String colFileName) {
////		RRadiusSubGraph[] rawSubGraphs = this.genRawSubGraphs(rank, rowFileName, colFileName);
//		
//		RRadiusSubGraph[] rawSubGraphs = graph.multiply(graph);
//		
//		ArrayList<RRadiusSubGraph> result = new ArrayList<RRadiusSubGraph>();
//		
//		for (int i = 0; i < rank; i++) {
//			RRadiusSubGraph rrsg = rawSubGraphs[i];
//			
//			if (rrsg != null) {
//				int[] vertexes = rrsg.getVertexes();
//				
//				boolean select = true;
//				
//				for (int j = 0; j < vertexes.length; j++) {
//					if (this.isContained(vertexes, vertexes[j])) {
//						select = false;
//						break;
//					}
//				}
//				
//				if (select) {
//					result.add(rrsg);
//				}
//			}
//		}
//		
//		this.allSubGraphs = result.toArray(new RRadiusSubGraph[result.size()]);
//	}
	
//	private RRadiusSubGraph[] genRawSubGraphs(int rank, String rowFileName, String colFileName) {
//		RRadiusSubGraph[] result = new RRadiusSubGraph[rank];
//		
//		try {
//			BufferedReader rowReader = new BufferedReader(new FileReader(rowFileName));
//			BufferedReader colReader = new BufferedReader(new FileReader(colFileName));
//			
//			String line = null;
//			
//			while (rowReader.ready() && colReader.ready()) {
//				line = rowReader.readLine().trim();
//				int row = rm.parseSN(line).intValue();
//				line = colReader.readLine().trim();
//				int col = rm.parseSN(line).intValue();
//				
//				RRadiusSubGraph rrsg = result[row - 1];
//				if (rrsg != null) {
//					rrsg.insertNode(col);
//				}
//				else {
//					rrsg = new RRadiusSubGraph(row);
//					rrsg.insertNode(col);
//					result[row - 1] = rrsg;
//					size++;
//				}
//			}
//		}
//		catch (FileNotFoundException ex) {
//			ex.printStackTrace();
//		}
//		catch (IOException ex) {
//			ex.printStackTrace();
//		}
//		
//		return result;
//	}
	
//	private boolean isContained(int[] vertexes, int vertex) {
//		RelationshipNode cursor = graph.getRowHeads().get(new Integer(vertex - 1));
//		
//		boolean result = true;
//		
//		for (int i = 0; i < vertexes.length; i++) {
//			if (result) {
//				result = false;
//				int v = vertexes[i];
//				RelationshipNode rn = null;
//				for (rn = cursor; rn != null; rn = rn.getNextNodeInSameRow()) {
//					if (v == rn.getColumn() + 1) {
//						result = true;
//						cursor = cursor.getNextNodeInSameRow();
//						break;
//					}
//					else if (v < rn.getColumn() + 1) {
//						return false;
//					}
//				}
//				
//				if (rn == null) {
//					return false;
//				}
//			}
//			
//		}
//		
//		return result;
//	}
	
//	public void genInvertedList() {
//		for (int i = 0; i < this.allSubGraphs.length; i++) {
//			RRadiusSubGraph rrsg = this.allSubGraphs[i];
//			int id = rrsg.getId();
//			SequentialIntArray nodes = rrsg.getNodes();
//			
//			for (int j = 0; j < nodes.getCapacity(); j++) {
//				if (this.invertedList[nodes.get(j) - 1] == null) {
//					this.invertedList[nodes.get(j) - 1] = new SequentialIntArray();
//				}
//				
//				this.invertedList[nodes.get(j) - 1].insert(id);
//			}
//		}
//	}
	
//	public void saveSubGraphs(SubGraphDB sgdb) {
//		for (int i = 0; i < this.allSubGraphs.length; i++) {
//			RRadiusSubGraph rrsg = this.allSubGraphs[i];
//			sgdb.insertSubGraph(rrsg);
//		}
//	}
	
//	public void saveInvertedList(SubGraphDB sgdb) {
//		for (int i = 0; i < this.invertedList.length; i++) {
//			if (this.invertedList[i].getCapacity() > 0) {
//				sgdb.insertAsstEntry(this.invertedList[i]);
//			}
//			else {
//				System.err.println("Error: found a vertex in no subgraph (" + i + ")");
//			}
//		}
//	}
	
	public void printAllSubGraphs(String file) {
		try {
			FileWriter fw = new FileWriter(file);
			this.printAllSubGraphs(fw);
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
	public void printAllSubGraphs(FileWriter fw) {
		try {
			this.sgdb.printSubGraphs(fw);
			
			fw.close();
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
//	public void printSubGraph(FileWriter fw, RRadiusSubGraph rrsg) {
//		try {
//			fw.write((rrsg.getRow() + 1) + "    ");
//			int[] vertexes = rrsg.getVertexes();
//			for (int j = 0; j < vertexes.length; j++) {
//				fw.write(vertexes[j] + ",");
//			}
//			
//			fw.write("\n");
//		}
//		catch (IOException ex) {
//			ex.printStackTrace();
//		}
//	}
	
	public void printInvertedList(String file) {
		try {
			FileWriter fw = new FileWriter(file);
			this.printInvertedList(fw);
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}
	
	public void printInvertedList(FileWriter fw) {
		try {
			this.sgdb.printInvList(fw);
			
			fw.close();
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
	}

}
